home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / oath.lha / oath / src / hashSet.cc < prev    next >
C/C++ Source or Header  |  1991-08-29  |  6KB  |  241 lines
  1. //***************************************************************************
  2. //             OATH :: Object-oriented Abstract Type Hierarchy
  3. //***************************************************************************
  4. //
  5. //  Copyright (C) 1991  Texas Instruments Incorporated
  6. //  Permission is granted to any individual or institution
  7. //  to use, copy, modify, and distribute this software,
  8. //  provided that this complete copyright and permission notice
  9. //  is maintained, intact, in all copies and supporting documentation.
  10. //
  11. //  Texas Instruments Incorporated provides this software "as is"
  12. //  without express or implied warranty.
  13. //
  14. //***************************************************************************
  15. //  hashSet (hashSetA, hashSetG)
  16. //
  17. //  History:
  18. //    07/91  Brian M Kennedy  import, export, typeRegister
  19. //    06/91  Brian M Kennedy  New macros & format; remove printDiagnostic
  20. //    04/91  Brian M Kennedy  Original
  21. //
  22. //***************************************************************************
  23.  
  24. #include "copyright.h"
  25.  
  26. #include <oath/hashSet.h>
  27.  
  28. #include <iostream.h>
  29.  
  30. /////////////////////////////////////////////////////////////////////////////
  31. /////////////////////////////////////////////////////////////////////////////
  32. // hashSet Outlines
  33.  
  34. OUTLINES(hashSet, set)
  35.  
  36. // Constructors //////////
  37.  
  38.     hashSetG::
  39. hashSetG (unsigned int IBuckets, int IsConst)
  40.    :setG(IsConst), Set(0), Count(0), Buckets(IBuckets)
  41.    {ref();
  42.         Set = (hashNodeP**)(new hashNodeP* [IBuckets]);
  43.     for(unsigned int I = 0; I < Buckets; I++)
  44.         Set[I] = 0;
  45.     deref();
  46.    }
  47.  
  48. // oathCore Operations //////////
  49.  
  50.     void hashSetG::
  51. export (exportP& X) const
  52.    {X.writeType(TypeName);
  53.     X.stream() << Buckets << ' ' << Count << (isConst() ? ' ' : '\0');
  54.     for(unsigned int I = 0; I < Buckets; ++I)
  55.         for(hashNodeP* N = Set[I]; N; N = N->Next)
  56.         N->Obj.export(X);
  57.    }
  58.  
  59.     objA hashSetG::
  60. import (importP& M)
  61.    {int Buckets, Count;
  62.     M.stream() >> Buckets >> Count;
  63.     char MakeConst = M.stream().get();
  64.     hashSetA HS = hashSetA::make(Buckets);
  65.     for(int I = 0; I < Count; ++I)
  66.         HS << objA::import(M);
  67.     if(MakeConst)
  68.         HS.guts()->forceConst();
  69.     return HS;
  70.    }
  71.  
  72.     void hashSetG::
  73. clearReferences()
  74.    {clearMark();
  75.     for(unsigned int I = 0; I < Buckets; ++I)
  76.         for(hashNodeP* N = Set[I]; N; N = N->Next)
  77.         N->Obj.guts()->deref();
  78.    }
  79.  
  80.     void hashSetG::
  81. setReferences()
  82.    {if(!isMarked())
  83.        {setMark();
  84.         for(unsigned int I = 0; I < Buckets; ++I)
  85.            {for(hashNodeP* N = Set[I]; N; N = N->Next)
  86.                {N->Obj.guts()->ref();
  87.             N->Obj.guts()->setReferences();
  88.            }
  89.        }
  90.        }
  91.    }
  92.  
  93.  
  94. // obj Operations //////////
  95.  
  96.     int hashSetG::
  97. isEqual (const objG* O) const
  98.    {if(!O->isType(setG::Type))
  99.         return FALSE;
  100.     else
  101.        {const setG* S = (const setG*)O;
  102.         if(Count != S->count())
  103.         return FALSE;
  104.     else
  105.        {for(unsigned int I = 0; I < Buckets; ++I)
  106.                {for(hashNodeP* N = Set[I]; N; N = N->Next)
  107.                {if(!S->contains(N->Obj.guts()))
  108.                 return FALSE;
  109.            }
  110.            }
  111.         return TRUE;
  112.        }
  113.        }
  114.    }
  115.  
  116.     objA hashSetG::
  117. makeCopy (int) const        // ignores MakeConst argument
  118.    {bagA HS = makeEmpty();
  119.     applyX(callSelf, HS.guts());
  120.     return HS;
  121.    }
  122.  
  123.  
  124. // bag Operations //////////
  125.  
  126.     int hashSetG::
  127. contains (const objG* O) const
  128.    {unsigned int Hash = hash(O);
  129.     return Set[Hash] && Set[Hash]->contains(O);
  130.    }
  131.  
  132.     int hashSetG::
  133. containsEqual (const objG* O) const
  134.    {ensure(contains(O), "Sorry, not implemented.");
  135.     return TRUE;
  136.    }
  137.  
  138.     int hashSetG::
  139. canContain (const objG*) const
  140.    {return TRUE;}
  141.  
  142.     void hashSetG::
  143. insert (const objG* O)
  144.    {NOT_CONST();
  145.     unsigned int Hash = hash(O);
  146.     Set[Hash] = new hashNodeP(O, Set[Hash]);
  147.    }
  148.  
  149.     void hashSetG::
  150. append (const bagG* B)
  151.    {NOT_CONST();
  152.     B->applyX(callSelf, this);
  153.    }
  154.  
  155.     void hashSetG::
  156. apply (void (*F)(objA)) const
  157.    {for(unsigned int I = 0; I < Buckets; ++I)
  158.         for(hashNodeP* N = Set[I]; N; N = N->Next)
  159.         F(N->Obj);
  160.    }
  161.  
  162.     bagG* hashSetG::
  163. applyX (objA (*F)(objA), bagG* B) const
  164.    {for(unsigned int I = 0; I < Buckets; ++I)
  165.        {for(hashNodeP* N = Set[I]; N; N = N->Next)
  166.        {objA R = F(N->Obj);
  167.         B->insert(R.guts());
  168.        }
  169.        }
  170.     return B;
  171.    }
  172.  
  173.     bagG* hashSetG::
  174. applyX (bagA (*F)(objA), bagG* B) const
  175.    {for(unsigned int I = 0; I < Buckets; ++I)
  176.        {for(hashNodeP* N = Set[I]; N; N = N->Next)
  177.        {bagA R = F(N->Obj);
  178.         B->append(R.guts());
  179.        }
  180.        }
  181.     return B;
  182.    }
  183.  
  184.     bagA hashSetG::
  185. makeEmpty () const
  186.    {return new hashSetG (Buckets);}
  187.  
  188.  
  189. // Set Operations //////////
  190.  
  191.     void hashSetG::
  192. remove (const objG* O)
  193.    {NOT_CONST();
  194.     unsigned int Hash = hash(O);
  195.     if(Set[Hash])
  196.         Set[Hash]->remove(O, Set[Hash]);
  197.    }
  198.  
  199.     void hashSetG::
  200. subtract (const setG* S)
  201.    {NOT_CONST();
  202.     for(unsigned int I = 0; I < Buckets; ++I)
  203.        {hashNodeP** L = &(Set[I]);
  204.         hashNodeP*  N = *L;
  205.     while(N)
  206.        {if(S->contains(N->Obj.guts()))
  207.            {*L = N->Next;
  208.             delete N;
  209.         N = *L;
  210.            }
  211.         else
  212.            {L = &(N->Next);
  213.             N = *L;
  214.            }
  215.        }
  216.        }
  217.    }
  218.  
  219.     void hashSetG::
  220. intersect (const setG* S)
  221.    {NOT_CONST();
  222.     for(unsigned int I = 0; I < Buckets; ++I)
  223.        {hashNodeP** L = &(Set[I]);
  224.         hashNodeP*  N = *L;
  225.     while(N)
  226.        {if(!S->contains(N->Obj.guts()))
  227.            {*L = N->Next;
  228.             delete N;
  229.         N = *L;
  230.            }
  231.         else
  232.            {L = &(N->Next);
  233.             N = *L;
  234.            }
  235.        }
  236.        }
  237.    }
  238.  
  239.  
  240. //***************************************************************************
  241.